/*
 * dom.cpp
 *
 *  Created on: Jul 18, 2010
 *      Author: vincent
 */
#include "flow.h"
#include <sstream>
#include <algorithm>
#include <cassert>

using namespace std;

DomTree::DomTree(CFG *c):Analysis<DomNode>(c){
    log.setDebug(false);
}

DomNode*    DomTree::createNode(BasicBlock *bb){
    return new DomNode(bb);
}

int DomTree::intersect(int dno1,int dno2){
    int last = cfg->getDfsBlockSize() - 1;
    int finger1 = last - dno1;  // to postorder
    int finger2 = last - dno2;  // to postorder
    BasicBlock *bb;
    const DomNode *idom;

    while(finger1 != finger2){
        while(finger1 < finger2){
            //cout<<"finger1 is "<<finger1<<endl;
            bb = cfg->getBlockByDfsno(last - finger1);
            idom = getOrCreateNode(bb)->getIdom();
            assert(idom && "idom is null");
            finger1 = last - idom->getBB()->getDfsNo();
        }
        while(finger2 < finger1){
            //cout<<"finger2 is "<<finger2<<endl;
            bb = cfg->getBlockByDfsno(last - finger2);
            idom = getOrCreateNode(bb)->getIdom();
            assert(idom && "idom is null");
            finger2 = last - idom->getBB()->getDfsNo();
        }
    }
    //return dfsOrder[last - finger1]->getDfsNo();
    return last -finger1;
}

/// Build Dominator Tree by
/// Keith D. Cooper,
/// Timothy J. Harvey and
/// Ken Kennedy
void DomTree::buildDomTree(){
    bool changed = true;

    //dfsOrder[0] is *start* block
    BasicBlock *start = cfg->getBlockByDfsno(0);
    BasicBlock *b1 = cfg->getBlockByDfsno(1);
    //dfsOrder[1]->setIdom(0);

    while(changed){
        changed = false;

        // in reverse postorder (exclude start block)
        for(CFG::dfs_iterator it = ++cfg->dfsBegin();it != cfg->dfsEnd();it++){
        //for(int i = 1;i < dfsOrder.size();i++){
            int new_idom = -1;

            BasicBlock *bb = *it;
            BasicBlock *pbb;
            BasicBlock::pred_iterator   pit;
            DomNode *node = getOrCreateNode(bb);

            for(pit = bb->getPredBegin();pit != bb->getPredEnd();pit++){
                pbb = *pit;
                // pick first processed predecessor
                if(pbb->getDfsNo() < bb->getDfsNo()){
                    new_idom = pbb->getDfsNo();
                    break;
                }
            }

            assert(new_idom != -1 && "can't find a processed predecessor");
            //cout<<"bb dfs no:"<<bb->getDfsNo()<<" idom:"<<bb->getIdom()<<" new_idom:"<<new_idom<<endl;

            for(pit = bb->getPredBegin();pit != bb->getPredEnd();pit++){
                pbb = *pit;
                if(pbb->getDfsNo() == new_idom){
                    continue;
                }

                if(getOrCreateNode(pbb)->getIdom()){
                    //log<<"intersect with "<<new_idom<<" and "<<pbb->getDfsNo()<<endl;
                    new_idom = intersect(new_idom,pbb->getDfsNo());
                }
            }

            DomNode *idom = node->getIdom();
            if(!idom || idom->getBB()->getDfsNo() != new_idom){
                //log<<"dfsno"<<bb->getDfsNo()<<" set to domno"<<new_idom<<endl;
                //bb->setIdom(new_idom);
                idom = getOrCreateNode(new_idom);
                node->setIdom(idom);
                idom->addDomee(node);
                changed = true;
            }
        } // for(int i = 1;i < dfsOrder.size();i++)
    } // while(changed)...
}

/// build the dominance frontier
void DomTree::buildDomFrontier(){
    CFG::dfs_reverse_iterator    dom_it;
    BasicBlock::succ_iterator   succ_it;
    set<BasicBlock*> visited;

    // in post order
    for(dom_it = cfg->dfsRbegin();dom_it != cfg->dfsRend();dom_it++){
        BasicBlock *bb = *dom_it;
        df_set_type&   dfset = domFrontiers[bb];

        if(visited.count(bb) != 0){
            continue;
        }
        visited.insert(bb);

        // calculate the DFlocal
        for(succ_it = bb->getSuccBegin();succ_it != bb->getSuccEnd();succ_it++){
            BasicBlock *succ_bb = *succ_it;
            DomNode *idom = getOrCreateNode(succ_bb)->getIdom();

            if(!idom || idom->getBB() != bb){
                int succNo = succ_bb->getDfsNo();
                //dfset.insert(dfsit - cfg->dfsBegin());
                //allDomFrontiers.insert(dfsit - dfsOrder.begin());
                dfset.insert(succNo);
                allDomFrontiers.insert(succNo);
            }
        }

        // calculate the DFup
        DomNode *node = getOrCreateNode(bb);
        for(DomNode::domee_iterator domee_it = node->begin();
            domee_it != node->end();domee_it++){
            BasicBlock  *domee_bb = (*domee_it)->getBB();
            df_set_type&  domee_dfset = domFrontiers[domee_bb];

            // the child of this node in domtree should be visited
            assert(visited.count(domee_bb) && "child has not been visited in domtree");
            for(df_set_type::iterator it = domee_dfset.begin();
                it != domee_dfset.end();it++){
                DomNode *idom = getOrCreateNode(*it)->getIdom();
                int  idom_dfsno = idom->getBB()->getDfsNo();
                //int idom_index = dfsOrder[*it]->getIdom();
                if(cfg->getBlockByDfsno(idom_dfsno) != bb){
                    dfset.insert(*it);
                    allDomFrontiers.insert(*it);
                }
            }
        }
    }

    log<<"frontiers: ";
    for(df_set_type::iterator it = allDomFrontiers.begin();it != allDomFrontiers.end();it++){
        log<<*it<<" ";
    }
    log<<endl;

    for(CFG::dfs_iterator dit = cfg->dfsBegin();dit != cfg->dfsEnd();dit++){
        BasicBlock *bb = *dit;
        df_set_type&   dfset = domFrontiers[bb];
        log<<"DF: Block"<<bb->getDfsNo()<<": ";
        for(df_set_type::iterator it = dfset.begin();it != dfset.end();it++){
            log<<cfg->getBlockByDfsno(*it)->getDfsNo()<<" ";
        }
        log<<endl;
    }
}

void DomTree::printBlocks(GraphPrinter &gp){
    string attrs[] = {"node [shape=box]","edge [color=green style=dotted]"};

    gp.beginSubgraph(cfg->getFunctionSymbol()->getName(),attrs,2);
    for(analysis_iterator it = nodes.begin();it != nodes.end();it++){
        stringstream ss;
        DomNode*    node = it->second;
        int fromNo = node->getBB()->getDfsNo();

        // don't gp.newNode here, as it will override the label printed in cfg
        for(DomNode::domee_iterator domee_it = node->begin();domee_it != node->end();domee_it++){
            int toNo = (*domee_it)->getBB()->getDfsNo();
            gp.newLine(fromNo,toNo);
        }
    }

    gp.endSubgraph();
}


